"""
quickSort
"""


def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left, (int, float)) else left
    right = len(arr) - 1 if not isinstance(right, (int, float)) else right
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex - 1)
        quickSort(arr, partitionIndex + 1, right)
    return arr


# 这种排序实际上是统计比基准数小的数字个数，最后把基准数放置到该位置
def partition(arr, left, right):
    if left >= right:
        return
    pivot = left
    index = pivot
    i = pivot + 1
    while i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index += 1
        i += 1
    swap(arr, pivot, index)
    print(index)
    return index


def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]


# arr = [1, 3, 5, 2, 7, 4, 6]
# quickSort(arr, 0, len(arr) - 1)
#
# print(arr)


def quickSort2(arr, left, right):
    if left < right:
        pivotIndex = partition2(arr, left, right)
        quickSort2(arr, left, pivotIndex - 1)
        quickSort2(arr, pivotIndex + 1, right)


def median3(arr, left, right):
    center = (left + right) // 2
    print(arr[left], arr[center], arr[right])

    if arr[left] > arr[center]:
        arr[left], arr[center] = arr[center], arr[left]
    if arr[left] > arr[right]:
        arr[left], arr[right] = arr[right], arr[left]
    if arr[center] > arr[right]:
        arr[center], arr[right] = arr[right], arr[center]

    pivot = arr[center]
    arr[center], arr[left] = arr[left], arr[center]
    return pivot


def partition2(arr, left, right):
    low = left
    high = right

    # 基准数可以取的随机一点
    pivot = median3(arr, left, right)
    while low < high:
        # 内层两个while循环顺序不能变，因为 如果先移动 左指针，最后左指针停下位置的数字必然比基准数大，
        # 最后和基准数交换就是错误的，所以让右指针先动，停留的数字就比基准数小，可以正确交换
        while arr[high] > pivot and low < high:
            high -= 1

        # 后半部出现的比基准数小的数字赋值给 arr[low] ,此时 low指针没动，可以被覆盖

        arr[low] = arr[high]

        while arr[low] <= pivot and low < high:
            low += 1

        arr[high] = arr[low]

    arr[low] = pivot
    return low


arr1 = [3, 2, 1, 5, 6, 4]

quickSort2(arr1, 0, len(arr1) - 1)

print(arr1)
